# Note: there is a better solution refer to disscuss of LeetCode

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        subs = []
        for sub in p.split('*'):
            subs.extend(sub.split('?'))

        for sub in subs:
            if len(s)!=0 and s.count(sub)==0:
                return False
        
        dp = [[False for _ in range(len(s)+1)] for _ in range(len(p)+1)]
        dp[-1][-1] = True
        for i in range(len(p)):
            if p[i]=='*':
                dp[i][-1] = True
            else:
                break
        for pi in range(len(p)):
            for si in range(len(s)):
                if p[pi]=='?':
                    dp[pi][si] = dp[pi-1][si-1]
                elif p[pi]=='*':
                    dp[pi][si] = dp[pi-1][si] or dp[pi-1][si-1] or dp[pi][si-1]
                elif p[pi]==s[si]:
                    dp[pi][si] = dp[pi-1][si-1]
                else:
                    dp[pi][si] = False
        return dp[len(p)-1][len(s)-1]

print(Solution().isMatch("aa","*"))